package 图;

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintStream;
import java.net.ServerSocket;
import java.net.Socket;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/13 15:26
 */
public class lc1976达到目的地的方案数 {


    /*
     ① : 计算 最短路径

     ② 递归 统计 最短路径的个数(因为 是求个数, 所以可以求缓存!)
     */
    public int countPaths(int n, int[][] roads) {
        int ans = 0;
        HashMap<Integer, Map<Integer, Integer>> graph = new HashMap<>(n); // 图节点的个数
        for (int i = 0; i < n; i++) {
            graph.put(i, new HashMap<>());
        }
        // 建图
        for (int road[] : roads) {
            graph.computeIfAbsent(road[0], t -> new HashMap<>()).put(road[1], road[2]);
            graph.computeIfAbsent(road[1], t -> new HashMap<>()).put(road[0], road[2]);
        }

        long dist[] = new long[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;

        // visited
        boolean[] vis = new boolean[n];

        /*
         dist[i] : 表示的 是 源点 到 节点 i 的最短路径距离( 此题的源点是 0)
         cnt[i] : 表示的是 源点 到 节点 i 的最短路径的个数!
         */
        int cnt[] = new int[n];
        cnt[0] = 1;

        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);

        // 加入初始值
        queue.add(new int[]{0, 0});// 这个 可不能少!

        while (!queue.isEmpty()) {
            int[] remove = queue.remove();

            for (Map.Entry<Integer, Integer> next : graph.get(remove[0]).entrySet()) {
                int dis = remove[1] + next.getValue();
//                int dis = (int)dist[remove[0]] + next.getValue();
                /*
                 这里有一个 非常大的 坑的点:  对于 该题而言

                 */
                if (!vis[next.getKey()] && dis < dist[next.getKey()]) {
                    dist[next.getKey()] = dis;

                    cnt[next.getKey()] = cnt[remove[0]]; // 继承前置节点的 个数

                    queue.add(new int[]{next.getKey(), dis});
                } else if (dis == dist[next.getKey()]) {
                    cnt[next.getKey()] = (cnt[next.getKey()] + cnt[remove[0]]) % 1000000007;
                }
            }
            vis[remove[0]] = true;
        }

        return cnt[n - 1];
    }





    /*
     思想滑坡了
     首先这个题 的 distance <= 10 ^ 9
     就注定不肯能进行 记忆忧搜索, 下面就是一个幻想的版本, 还是得 从dijkstra 下手!
     */


    private int recursion(int node, int n, HashMap<Integer, Map<Integer, Integer>> graph, int distance, int[] dp, boolean vis[]) {
//        if(distance == 0 && node == n - 1){
//            return 1;
//        }
        if (distance < 0) {
            return 0;
        }
        if (node == n - 1) {
            return distance == 0 ? 1 : 0;
        }
        if (dp[node] != -1) {
            return dp[node];
        }

        int ans = 0;
        for (Map.Entry<Integer, Integer> next : graph.get(node).entrySet()) {
            if (!vis[next.getKey()]) {
                vis[next.getKey()] = true;
                ans += recursion(next.getKey(), n, graph, distance - next.getValue(), dp, vis);
                vis[next.getKey()] = false;
            }
        }
        return dp[node] = ans;
    }


    public int solution(int n,int [][]roads) {
        Map<Integer,Map<Integer,Integer>> graph = new HashMap<>(n);
        for (int i = 0; i < n; i++) {
            graph.put(i, new HashMap<>());
        }

        for(int road[] :  roads){
            graph.get(road[0]).put(road[1],road[2]);
            graph.get(road[1]).put(road[0],road[2]);
        }

        int dist[] = new int[n]; //  dist【i】 ：表示的是， i 到 源点 的最短路径

        Arrays.fill(dist,Integer.MAX_VALUE); //  这一步 总是 他妈的忘！

        boolean vis[] = new boolean[n]; // 锁定数组， 已经锁死的走过的路

        int path[] = new int[n];

        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]); //  这一步也总是他妈的忘！
        dist[0] = 0;
        path[0] = 1;
        queue.add(new int[]{0,0});
        while(!queue.isEmpty()){
            int[] remove = queue.remove();
            for (Map.Entry<Integer, Integer> entry : graph.get(remove[0]).entrySet()) {
                if(vis[entry.getKey()]) {
                    continue;
                }
                int dis = remove[1] + entry.getValue();
                if(dis < dist[entry.getKey()]){
                    dist[entry.getKey()] = dis;
                    queue.add(new int[]{entry.getKey(),dis});
                    path[entry.getKey()] = path[remove[0]];
                }
                else if(dis == dist[entry.getKey()]){
                    path[entry.getKey()] += path[remove[0]];
                }
            }
            vis[remove[0]] = true; // EEEE
        }
        return path[n - 1];
    }



    public int solve(int n,int [][]roads){
        Map<Integer,Map<Integer,Integer>> graph = new HashMap<>(n);


        for(int i = 0;i < n;i++){
            graph.put(i,new HashMap<>());
        }

        for(int road[] : roads){
            graph.get(road[0]).put(road[1],road[2]);
            graph.get(road[1]).put(road[0],road[2]);
        }

        int dist[] = new int[n];

        Arrays.fill(dist,Integer.MAX_VALUE);
        int path[] = new int[n];

        boolean []vis = new boolean[n];


        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b) -> a[1] - b[1]);
        dist[0] = 0;
        path[0] = 1;
        queue.add(new int[]{0,0});
        while(!queue.isEmpty()){
            int[] remove = queue.remove();
            for (Map.Entry<Integer, Integer> entry : graph.get(remove[0]).entrySet()) {
                if(vis[entry.getKey()]){
                    continue;
                }
                int dis = remove[1] + entry.getValue();
                if(dis < dist[entry.getKey()]){
                    dist[entry.getKey()] = dis;
                    queue.add(new int[]{entry.getKey(),dis});
                    path[entry.getKey()] = path[remove[0]];
                 }else if(dis == dist[entry.getKey()]){
                    path[entry.getKey()] = (path[entry.getKey()] + path[remove[0]]) % 1000000007;
                }
            }
        }


        return path[n - 1];
    }

    /*
     BIO:

    什么是 程序的 block： 在 应用程序 和 内核程序 发生系统调用的时候， 应用程序 在 等待 内核程序 函数返回的过程


     */
    public static void main(String[] args) throws IOException {
        ServerSocket serverSocket = new ServerSocket(9090); // 创建一个服务端的socket

        System.out.println("创建了一个服务端Socket， 并注册 端口号 为9090"); // 系统调用

        while(true){
            System.in.read();  // 系统调用

            final Socket client = serverSocket.accept(); // 系统调用

            System.out.println("请求连接的 socket 的端口号："  + client.getPort()); // 系统调用

            new Thread(()->{
                InputStream in = null;
                try{
                    in = client.getInputStream();
                }catch (Exception e){

                }finally {
                    // 释放资源！
                }
            }).start();

        }

    }

}
